The continually increasing complexity of polygonal models for computer display applications has tended to outpace the advances made in hardware technology. As such, the rendering of complex polygonal models, at interactive rates, remains a challenging task. The various techniques developed to address this problem can be classified into three main categories; geometry-based, image-based, and hybrid.
The hybrid method combines the use of three dimensional geometric modeling with two dimensional images in an attempt to draw on the strengths of both the geometry-based and image-based categories. The underlying strategy is to render those parts of the model close to the viewer as geometry, i.e., as a three dimensional (3D) model, and to render more distant visible parts as two dimensional (2D) images. Such schemes offer the advantage of increased performance in cases where geometry-based simplification techniques (e.g., visibility culling) break down, and the rendering time is proportional to the size of the nearby geometry and the number of images used. Moreover, the amount of storage required is considerably reduced as compared to image-based methods. Hybrid techniques are also well suited to the transmission of large models over networks.
To avoid long delays between the time of a request and the subsequent display of the model, adaptive techniques that combine different transmission methods have been proposed. For example, to deliver a 3D scene from a server to a client, a panoramic image of the scene could be transmitted first to provide the client with a quick view of the model. Subsequently, 3D geometric objects are transmitted to progressively replace parts of the panorama as they are received by the client.
One significant problem to be addressed when implementing algorithms that combine images with geometry are so-called `occlusion errors`. Occlusion errors occur when previously hidden areas of an image become visible, as objects in the scene move. For example, contrast FIG. 1A to FIG. 1B, and note the existence of the occlusion errors (OEs) in FIG. 1B due to the movement of the objects to the right in the drawing. The occurrence of occlusion errors is objectionable to most users, and can seriously degrade a desired illusion of realism being conveyed by a displayed scene and object(s).
In order to deal with these occlusion errors several strategies have been proposed. A first strategy is based on the use of a "neutral" fill color, while a second strategy is based on an interpolation of the colors of the pixels that surround the occlusion error. A discussion of both of these strategies can be found in a publication by Bengt-Olaf Schneider and Linus Vepstas, Extending VRML to Support Panoramic Images. A third strategy is based on the use of multiple layer images, as proposed by Schaufler et al., Per-Object Image Warping with Layered Impostors, Proceedings of the 9.sup.th Eurographics Workshop on Rendering, 1998.
Unfortunately, these various strategies typically either yield very rough approximations of the scene behind the objects that have moved, or require a considerable amount of additional storage and non-trivial computation to fill in the gaps resulting from the occlusion errors.
It will become apparent below that a capability to embed data into a 3D geometric object is an important aspect of this invention. It is thus made of record that various techniques for data embedding have been previously investigated for still images, video and audio data, texts, and 3D geometric models. Reference in this regard can be had to: Mintzer et al., Effective and Ineffective Digital Watermarks, Proceedings 1997 International Conference on Image Processing, pp.9-12, 1997; and Memon et al., Protecting Digital Media Content, Communications of the ACM, 41(7), pp. 35-43, 1998.
In the case of 3D models, the annotations of scene description formats such a Virtual Reality Modeling Language (VRML) have been the primary means for adding such information (see Carey et al., The Annotated VRML 2.0 Reference Manual, Addison Wesley, 1997.) More recently, techniques for embedding watermarks into the geometry of models have been proposed by Ohbuchi et al., Watermarking Three Dimensional Polygonal Models Through Geometric and Topological Modifications, Journal of Selected Areas in Communications, 16(4), pp. 551-560, 1998.
However, these known data embedding techniques are generally limited to the encoding of relatively small amounts of information, mainly text, into objects, and are primarily targeted towards security applications, such as copyright protection, theft deterrence, and inventories. In other words, these conventional data embedding techniques do not suggest or provide a solution to the occlusion problem.